class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1);
        dp[0]=0;
        int ret=-0x3f3f3f3f;
        for(int i=1;i<n+1;i++)
        {
            dp[i] = max(dp[i-1]+nums[i-1],nums[i-1]);
            if(dp[i]>ret)
            {
                ret = dp[i];
            }
        }
        return ret;
    }
};